//输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 
//
// 示例 1: 
//
// 输入: n = 1
//输出: [1,2,3,4,5,6,7,8,9]
// 
//
// 
//
// 说明： 
//
// 
// 用返回一个整数列表来代替打印 
// n 为正整数 
// 
// Related Topics 数组 数学 👍 227 👎 0


package leetcode.editor.cn;

//Java：打印从1到最大的n位数

import com.leetcode.utils.PrintUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
 */
public class DaYinCong1daoZuiDaDeNweiShuLcof {
    public static void main(String[] args) {
        Solution solution = new DaYinCong1daoZuiDaDeNweiShuLcof().new Solution();
        // TO TEST
        PrintUtil.printArray(solution.printNumbers(10));
//        System.out.println('9' + 1 - 48);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] printNumbers(int n) {

            // 没有考虑大数
            char[] nums = new char[n];
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                nums[i] = '0';
            }

            // 如果没有溢出，就进行打印
            while (!increment(nums, list)) {
                print(nums, list);
            }


            int[] result = new int[list.size()];
            for (int i = 0; i < result.length; i++) {
                result[i] = list.get(i);
            }
            return result;
        }

        /**
         * 每次实现字符 + 1
         *
         * @param nums
         * @param list
         * @return
         */
        public boolean increment(char[] nums, List<Integer> list) {
            // 是否溢出的标志
            boolean isTakeOver = false;
            int isCarry = 0;
            int nsum = 0;
            int nlen = nums.length;
            for (int i = nlen - 1; i >= 0; i--) {
                nsum = nums[i] - '0' + isCarry;
                if (i == nlen - 1) {
                    nsum++;
                }
                if (nsum >= 10) {
                    nsum = nsum - 10;
                    if (i == 0) {
                        isTakeOver = true;
                        break;
                    } else {
                        // 进入下一位的计算
                        isCarry = 1;
                        nums[i] = (char) (nsum + '0');
                    }
                } else {
                    // 退出循环，进行打印
                    nums[i] = (char) (nsum + '0');
                    break;
                }
            }
            return isTakeOver;
        }

        public void print(char[] nums, List<Integer> list) {
            StringBuffer sb = new StringBuffer("");
            for (int i = 0; i < nums.length; i++) {
                // 查找第一个不为0的字符
                if (nums[i] != '0') {
                    for (int j = i; j < nums.length; j++) {
                        sb.append(nums[j]);
                    }
                    break;
                }
            }
            list.add(Integer.parseInt(sb.toString()));
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
